import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

class Solution {
    public static List<Integer> findAnagrams(String s, String p) {
        int left = 0,right = 0;
        char[] hash1 = new char[s.length()];
        char[] hash2 = new char[p.length()];
        int[] array1 = new int[128];
        int[] array2 = new int[128];
        hash1 = s.toCharArray();
        hash2 = p.toCharArray();
        List<Integer> ret = new ArrayList<>();
        for(; right < p.length(); right++) {
            array2[hash2[right]]++;
        }
        for(int i = 0; i < p.length(); i++) {
            array1[hash1[i]]++;
        }
        while(right < s.length()) {
            if(Arrays.equals(array1,array2)) {
                ret.add(left);
            }
            array1[hash1[left]]--;
            left++;
            array1[hash1[right]]++;
            right++;
        }
        if(Arrays.equals(array1,array2)) {
            ret.add(left);
        }
        return ret;
    }

    public static List<Integer> findAnagrams1(String s, String p) {
        List<Integer> ret = new ArrayList<>();
        int left = 0, right = 0, count = 0;
        char[] hash1 = s.toCharArray();
        char[] hash2 = p.toCharArray();
        int[] array1 = new int[26];
        int[] array2 = new int[26];
        for (char a : hash2) {
            array2[a - 'a']++;
        }
        while(right < s.length()) {
            array1[hash1[right]-'a']++;
            if(array1[hash1[right]-'a'] <= array2[hash1[right]-'a']) count++;
            if(right - left + 1 > p.length()) {
                if(array1[hash1[left] - 'a'] <= array2[hash1[left] - 'a']) {
                    count--;
                }
                array1[hash1[left] - 'a']--;
                left++;
            }
            if(count== p.length()) {
                ret.add(left);
            }
            right++;
        }
        return ret;
    }

    public static void main(String[] args) {
        String s = "cbaebabacd";
        String p = "abc";
        List<Integer> ret = findAnagrams1(s,p);
        System.out.println(ret);
    }
}